1. Field of the Invention
The present invention relates to data systems. More specifically, the present invention relates to processing data transactions without violating ordering rules.
2. Discussion of Related Art
Modern data systems typically follow a producer-consumer model. FIG. 1 shows a data system 100 having a consumer 110, a data storage device 120, a bus 130, a bridge 140, a bus 150, a producer 160, a flag register 170, and a status register 180. In a producer-consumer model, producer 160 produces data and consumer 110 consumes (i.e., uses) the data. Specifically, when requested, producer 160 writes data into data storage device 120 through bus 150, bridge 140, and bus 130. After writing data into data storage device 120, producer 160 sets a flag in flag register 170 to indicate that the data has been written into data storage device 120. Consumer 110 waits until the flag is set in flag register 170 before using the data in data storage device 120. Consumer 110 also resets the flag in flag register 170 and writes a completion status code in status register 180 to indicate that consumer 110 has consumed the data. FIG. 1 shows one example of the producer-consumer model. In actual implementation, each component (i.e., consumer, producer, data storage device, flag register, and status register) of the producer-consumer model can be placed on either side of the bridge.
Data systems generally support multiple transaction types, such as posted transactions (e.g., data writes not requiring a response), non-posted transactions (e.g., data read requests), and completion transactions (e.g., data in response to data read requests. To handle the various transaction types, a transaction queue for each transaction type can be used. FIG. 2(a) shows a series of transactions 200, which includes (in order) a posted transaction P_01, a non-posted transaction NP_02, a completion transaction C_03, a posted transaction P_04, a non-posted transaction NP_05, a non-posted transaction NP_06, a posted transaction P_07, a completion transaction C_08, a posted transaction P_09, and a posted transaction P_10.
As illustrated in FIG. 2(b), the transactions of FIG. 2 are placed into type specific transaction queues in the order the transactions are received, such as, a posted transaction queue 210, a non-posted transaction queue 220, and a completion transaction queue 230. Specifically, posted transactions P_01, P_04, P_07, P_09, and P_10 are placed in posted transaction queue 210; non-posted transactions NP_02, NP_05, and NP_06 are placed in non-posted transaction queue 220; and completion transactions C_03 and C_08 are placed in completion transaction queue 230. Transactions of the same type are processed in the order received. However, transactions of different type are allowed to pass previously issued transaction of another type under certain ordering rules. For example, in one interpretation of the ordering rules of a PCI or PCI Express bus, posted transaction are allowed to pass previously received non-posted transactions and previously received completion transactions. Non-posted transactions are allowed to pass previously received completion instructions but not allowed to pass previously received posted transactions. Completion instructions are allowed to pass previously received non-posted transaction but not allowed to pass previously received posted instructions. These ordering rules are to prevent a consumer (in the producer-consumer model) from consuming data before a producer is finished and to prevent a producer from producing data before a consumer is finished. These ordering rules are summarized in Table 1. Table 1 indicates whether the transaction type in the first column may pass the previously issued transaction of the transaction types in the following columns.
TABLE 1TransactionPostedNon-PostedCompletionPOSTEDNOYESYESNON-POSTEDNONOYESCOMPLETIONNOYESYES
Improved bandwidth is achieved when some transaction types are blocked for whatever reason but another transaction type can proceed without violating the ordering rules. For example, after posted transaction P_01 completes, if non-posted transaction NP_02 is blocked, completion transaction C_03 and posted transaction P_04 are allowed to proceed ahead of non-posted transaction NP_02. Thus, a blocked transaction does not necessarily halt usage of the data system. However, due to the ordering rules, blocked posted transactions may halt usage of the data system until the block is resolved.
For example, if posted transaction P_01 is blocked, no other transaction can be processed because neither non-posted transactions nor completion transactions are allowed to pass a previously received posted transaction. However, if posted transaction P_04 is blocked (after posted transaction P_01 has already been processed), non-posted transaction NP_02 and completion transaction C_03 can proceed. If posted transaction P_04 is still blocked after non-posted transaction NP_02 has been processed, non-posted transaction NP_05 is blocked by the ordering rules, because non-posted transaction NP_05 is not allowed to pass the previously received posted instruction P_04.
Thus, when processing the transaction, the information relating to the original order that the transactions were received is needed to follow the ordering rules. However, once the transactions have been separated into the various type-specific transaction queues, the original order of the transaction cannot be reconstructed from the transactions queues. However, the order of the transactions within each transaction type is preserved in the transaction queue. Conventionally, a transaction sequence number has been added to each transaction as the transaction is stored in the transaction queues. However, the transaction sequence number increases the size of the transaction queue by approximately 10%. Alternatively, an additional memory may be used to store the transaction sequence numbers. However, the additional memory increases the complexity of the data system.
Hence, there is a need for a method or system that can process transactions in the transaction queues in accordance with the ordering rules without requiring the increased queue size or additional complexity of using a transaction sequence number.